package com.hanxiaozhang.no10leetcode.array;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈最大子序和〉
 * <p>
 * 给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），
 * 返回其最大和。子数组是数组中的一个连续部分。
 * <p>
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1]的和最大，为6 。
 * <p>
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 * <p>
 * 示例 3：
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 * <p>
 * 思路：动态规划
 * 1. 定义状态表  int[nums.length]
 * 2. 初始化边界值 int[0]=0
 * 3. 构建状态转移方程：
 *  -- 前提条件：i > 0   =>  因为0是边界条件值
 *  -- 情况1：加上之前 [i -1]元素的最大字段和
 *  -- 情况2：不加上之前[i -1] 元素的最大字段和，即当前元素
 *  -- 汇总：max（情况1,情况2）
 * 4. 选择最优子结构（根据记忆表的值，计算每一步的最优值） -> 循环每一步方程
 * 5. 回溯求解（遍历记忆表，找出最优解）
 *
 * @author hanxinghua
 * @create 2023/12/8
 * @since 1.0.0
 */
public class No53MaximumSubarray {

    public static void main(String[] args) {

        int[] nums = {1};

        int[] nums1 = {1, 2};

        int[] nums2 = {5, 4, -1, 7, 8};

        int[] nums3 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        method3(nums3);

    }

    /**
     * 参考com.hanxiaozhang.no3algorithm.dynamicprogramming.No2MaxSubArraySum
     *
     * @param nums
     * @return
     */
    private static Integer method3(int[] nums) {

        int max = 0;

        // 1. 定义状态表
        int[] result = new int[nums.length];

        // 2. 初始化边界值
        result[0] = nums[0];

        // 4. 选择最优子结构（根据记忆表的值，计算每一步的最优值）
        for (int i = 1; i < nums.length; i++) {

            // 3. 构建状态转移方程：
            // 前提条件：i > 0   =>  因为0是边界条件值
            // 情况1：加上之前 [i -1]元素的最大字段和
            // 情况2：不加上之前[i -1] 元素的最大字段和，即当前元素
            // 汇总：max（情况1,情况2）
            result[i] = Math.max(result[i - 1] + nums[i], nums[i]);

            // 5.回溯求解（遍历记忆表，找出最优解）
            if (result[i] > max) {
                max = result[i];
            }

        }
        System.out.println("max is " + max);
        return max;
    }


    /**
     * 笨方法2
     *
     * @param nums
     * @return
     */
    private static Integer method2(int[] nums) {

        if (nums.length == 0) {
            return null;
        }

        if (nums.length == 1) {
            return nums[1];
        }

        int startPos = 0, endPos = 0, max = 0, temp = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; i++) {
                temp = 0;
                for (int k = i; k <= j; k++) {
                    temp += nums[k];
                }
                if (temp > max) {
                    max = temp;
                    startPos = i;
                    endPos = j;
                }

            }
        }

        System.out.println("subarray is " + Arrays.toString(Arrays.copyOfRange(nums, startPos, endPos + 1)) +
                " max is " + max
        );

        return max;
    }


    /**
     * 笨方法1
     *
     * @param nums
     * @return
     */
    private static Integer method1(int[] nums) {

        if (nums.length == 0) {
            return null;
        }

        if (nums.length == 1) {
            return nums[1];
        }

        int startPos = 0, endPos = 0, max = 0, temp = 0;

        // 模拟每个子序列的起点
        for (int i = 0; i < nums.length; i++) {
            // 模拟每个子序列的终点
            for (int j = nums.length - 1; j > 0; j--) {
                if (i == j) {
                    continue;
                }
                temp = 0;
                for (int k = i; k <= j; k++) {
                    temp += nums[k];
                }
                if (temp > max) {
                    max = temp;
                    startPos = i;
                    endPos = j;
                }
            }
        }

        System.out.println("subarray is " + Arrays.toString(Arrays.copyOfRange(nums, startPos, endPos + 1)) +
                " max is " + max
        );

        return max;
    }


}
